#include <atomic>
#include <stdio.h>
#include <threads.h>

#include "model-assert.h"

using namespace std;


template<typename T>
class LockFreeStack {
    using Ptr = T*;
public:

    void push(T t) {
        Node *node = new Node(new T(t), head_.load());
        while (!head_.compare_exchange_weak(node->next_, node));
    }

    Ptr pop() {
        ++threadsInPop_;
        Node* head = head_.load();
        while(head && !head_.compare_exchange_weak(head, head->next_));
        Ptr ret = nullptr; //空栈返回空指针

        //从节点提取数据，节点可能不立即删除，但是如果返回的数据一旦不需要(例如不保存返回值)就立即被删除
        if (head) ret = head->data_;

        try_reclaim(head);
        return ret;
    }

private:
    struct Node {
        Ptr data_;
        Node *next_;
        Node(Ptr data, Node* next = nullptr)
                : data_(data)
                , next_(next)
        {}
    };
    static void delete_nodes(Node *nodes) {
        Node *node;
        while (nodes) {
            node = nodes;
            nodes = nodes->next_;
            delete node;
        }
    }

    void try_reclaim(Node *oldHead) {
        if (threadsInPop_.load() == 1) {
            Node *deletedNodes = deletedNodes_.exchange(nullptr);   //接手候删链表
            if (!--threadsInPop_) {
                delete_nodes(deletedNodes);
            } else if (deletedNodes) {
                chain_pending_nodes(deletedNodes);
            }
            delete oldHead;
        } else {
            chain_pending_node(oldHead);
            --threadsInPop_;
        }
    }

    //将deletedNodes链表接在nodes链表后面
    void chain_pending_nodes(Node* nodes) {
        Node *last = nodes;
        while (last->next_) {
            last = last->next_;
        }
        chain_pending_nodes(nodes, last);
    }

    void chain_pending_nodes(Node* first, Node* last) {
        last->next_ = deletedNodes_.load();
        while (!deletedNodes_.compare_exchange_weak(last->next_, first));
    }

    //将deletedNodes链表接在节点n后面
    void chain_pending_node(Node *n) {
        chain_pending_nodes(n, n);
    }

    std::atomic<Node*> head_;     //链表头节点，用来模拟栈
    std::atomic<int> threadsInPop_;     //运行pop的线程个数
    std::atomic<Node*> deletedNodes_; //候删节点链表
};


LockFreeStack<int> stk;
constexpr int kMax = 10;

void produce() {
    for (int i = 0; i < kMax; ++i) {
        stk.push(i);
    }
}

void consume() {
    int *p;
    int cnt = 0;
    while (cnt < kMax) {
        while (!(p = stk.pop()));
        //std::cout << *p << std::endl;
        printf("%d\n", *p);
	++cnt;
        delete p;
    }
}

int user_main(int argc, char **argv) {
//int main(int argc, char **argv) {
    thrd_t t1, t2;
    thrd_create(&t1, (thrd_start_t)&produce, NULL);
    thrd_create(&t2, (thrd_start_t)&consume, NULL);
    thrd_join(t1);
    thrd_join(t2);
    return 0;
}

